
public class LeetCode148 {
    class Solution {
        public ListNode sortList(ListNode head) {
            // 如果链表为空或者只有一个节点，则已经是有序的
            if (head == null || head.next == null) {
                return head;
            }

            // 使用快慢指针找到链表的中间点
            ListNode mid = findMid(head);
            ListNode rightHead = mid.next;

            // 断开链表为两部分
            mid.next = null;

            // 递归地对左右两部分分别排序
            ListNode left = sortList(head);
            ListNode right = sortList(rightHead);

            // 合并两个有序链表
            return merge(left, right);
        }

        private ListNode findMid(ListNode head) {
            // 使用快慢指针找到链表的中间点
            ListNode slow = head, fast = head;
            while (fast.next != null && fast.next.next != null) {
                slow = slow.next;
                fast = fast.next.next;
            }
            return slow;
        }

        private ListNode merge(ListNode l1, ListNode l2) {
            // 创建一个哨兵节点作为合并后链表的起点
            ListNode dummy = new ListNode(0);
            ListNode current = dummy;

            // 比较两个链表的节点值，将较小的节点连接到结果链表
            while (l1 != null && l2 != null) {
                if (l1.val < l2.val) {
                    current.next = l1;
                    l1 = l1.next;
                } else {
                    current.next = l2;
                    l2 = l2.next;
                }
                current = current.next;
            }

            // 将剩余的节点连接到结果链表
            current.next = (l1 != null) ? l1 : l2;

            // 返回合并后的链表（跳过哨兵节点）
            return dummy.next;
        }
    }
}
